The invention relates to computer graphics and, in particular, to the culling of occluded polygons from a scene being rendered in a tiled, three-dimensional computer graphics architecture.
In the field of data processing, there is an ever increasing demand for graphics and full-motion video applications which are faster, more detailed, and generally more lifelike than their predecessors. Many of these applications are useful in commercial, educational, military, and personal data processing systems. In addition, the rapid acceleration of Internet applications is mandating high performance graphics and multimedia features in newly released computer systems.
High speed three-dimensional (3D) graphics processing requires fast, pipelined processing in order to provide realistic detail and to implement special effects, such as texture maps, lighting, alpha blending, and Z-buffering.
Texture maps provide life-like surfaces and shadows within a three-dimensional image. Lighting provides realistic approximations of the effect of light from various sources striking objects. Alpha blending allows two graphics objects to be blended together.
Z-buffering (or hidden surface removal) tracks the depth of objects or pixels to ensure that a minimum of processing is carried out on polygons which are hidden behind others in a scene. Z-buffering has become increasingly important in graphical processing systems, because the size and complexity of graphical databases have been growing for many 3D graphics applications. These 3D graphics models typically have high depth complexity, i.e. a given pixel is rendered many times due to many overlapping polygons, and only the polygon closest to the viewer ends up being visible.
Identifying and culling these occluded polygons represents a significant performance improvement opportunity. In general, low cost graphics accelerators have not yet been able to incorporate effective occlusion culling. Previously proposed occlusion culling algorithms have been too complex for integration into low cost architectures.
Graphics processing architectures must address both the computational load of transformations, texturing, and lighting, as well as the increasingly important bandwidth load of accessing the geometry, texture, and visibility data. To be commercially successful, graphics accelerators for personal computers must address these computation and bandwidth requirements while keeping the hardware cost very low.
High output bandwidth implies high cost memory for Z-buffering and for anti-aliasing (reducing stair-stepping or jagged lines that sometimes occur on a display screen). This cost can be kept down by using a tiled architecture that renders the scene one tile or chunk at a time and reuses the fast expensive memory for each tile.
The Z-buffer provides a basic hidden surface removal mechanism for graphics, accelerators used in personal computers, despite its lack of support for occlusion culling. Major performance improvements can be achieved by identifying and eliminating those polygons that cannot be seen from some regions of space. This saves the cost of rendering such polygons by scan converting, lighting, alpha-blending, shading, and/or texturing them.
Software algorithms are currently known for processing, including culling, polygons, in computer graphics systems. However, these algorithms have either required complex and costly computer hardware to implement, or they have provided unsatisfactory performance.
For the reasons stated above, there is a substantial need in the area of computer graphics processing to provide a graphics processing system which can render high depth complexity scenes while reducing both computational and bandwidth loads.
In addition, there is a substantial need in the area of computer graphics processing to provide computer graphics hardware which can efficiently perform high depth complexity graphics processing and which is relatively inexpensive to manufacture.
Accordingly, in one embodiment of the invention there is provided a method for use in a processor adapted to be used in a graphical data processing system. The data processing system comprises a frame buffer and a Z-buffer. The method operates to cull occluded polygons from a scene being assembled in the frame buffer. The method comprises rendering the polygons in each tile of the scene in depth order, starting with a closest polygon, and storing their pixel depths in the Z-buffer. As polygons are rendered, an evaluation is made whether a coverage parameter has been satisfied and, if so, a hierarchical Z-buffer is constructed from the Z-buffer. Subsequent polygons are compared to the hierarchical Z-buffer to determine whether they are completely hidden and, if so, they are culled. Additional embodiments are described and claimed.